package com.lili.sort;

/**
 * @Auther: 李 力
 * @Date: 2024/8/1
 * @Description: 希尔排序
 * @version: 1.0
 */
public class ShellSort {
    /*
     * 希尔排序实际上是对插入排序的优化
     * 时间复杂度: 最好O(nlogn) 最坏O(n^2)  平均O(nlogn)
     * 空间复杂度: O(1)
     */
    public static int[] shellSort(int[] arr) {
        //间隙选择:初始值可以为arr.length/2，然后每次都除2
        for (int gap = arr.length >>> 1; gap >= 1; gap = gap >>> 1) {
            for (int low = gap; low < arr.length; low++) {
                int t = arr[low];
                int i = low - gap;
                while (i >= 0 && arr[i] > t) {
                    arr[i + gap] = arr[i];
                    i = i - gap;
                }
                if (i != low - gap) {
                    arr[i + gap] = t;
                }
            }
        }
        return arr;
    }
}
